{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Unique Paths II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: uniquePathsWithObstacles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #不同路径 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个机器人位于一个<meta charset=\"UTF-8\" />&nbsp;<code>m x n</code>&nbsp;网格的左上角 （起始点在下图中标记为 “Start” ）。</p>\n",
    "\n",
    "<p>机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。</p>\n",
    "\n",
    "<p>现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？</p>\n",
    "\n",
    "<p>网格中的障碍物和空位置分别用 <code>1</code> 和 <code>0</code> 来表示。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/04/robot1.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>3x3 网格的正中间有一个障碍物。\n",
    "从左上角到右下角一共有 <code>2</code> 条不同的路径：\n",
    "1. 向右 -&gt; 向右 -&gt; 向下 -&gt; 向下\n",
    "2. 向下 -&gt; 向下 -&gt; 向右 -&gt; 向右\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/04/robot2.jpg\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>obstacleGrid = [[0,1],[0,0]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m ==&nbsp;obstacleGrid.length</code></li>\n",
    "\t<li><code>n ==&nbsp;obstacleGrid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>obstacleGrid[i][j]</code> 为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [unique-paths-ii](https://leetcode.cn/problems/unique-paths-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [unique-paths-ii](https://leetcode.cn/problems/unique-paths-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0,0],[0,1,0],[0,0,0]]', '[[0,1],[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        @cache\n",
    "        def getPaths(x, y):\n",
    "            if obstacleGrid[x][y] == 1:\n",
    "                return 0\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return 1\n",
    "            if x == m - 1:\n",
    "                return getPaths(x, y+1)\n",
    "            if y == n - 1:\n",
    "                return getPaths(x+1, y)\n",
    "            return getPaths(x+1, y) + getPaths(x, y+1)\n",
    "        return getPaths(0, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: 'List[List[int]]') -> 'int':\n",
    "        n = len(obstacleGrid)\n",
    "        m = len(obstacleGrid[0])\n",
    "        memo = obstacleGrid\n",
    "        if memo[-1][-1] or memo[0][0]:\n",
    "            return 0\n",
    "        memo[-1][-1] = -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                if memo[i][j]:\n",
    "                    continue\n",
    "                if i < n - 1 and memo[i + 1][j] < 0:\n",
    "                    memo[i][j] += memo[i + 1][j]\n",
    "                if j < m - 1 and memo[i][j + 1] < 0:\n",
    "                    memo[i][j] += memo[i][j + 1]\n",
    "        return -memo[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if obstacleGrid == [] or obstacleGrid[0] == []:\n",
    "            return 0\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return 0\n",
    "        DP = []\n",
    "        for i in range(len(obstacleGrid)):\n",
    "            tmp = []\n",
    "            for j in range(len(obstacleGrid[0])):\n",
    "                if i == 0:\n",
    "                    if j == 0:\n",
    "                        tmp.append(1)\n",
    "                    elif obstacleGrid[i][j] == 0:\n",
    "                        tmp.append(tmp[-1])\n",
    "                    else:\n",
    "                        tmp.append(0)\n",
    "                else:\n",
    "                    if obstacleGrid[i][j] == 1:\n",
    "                        tmp.append(0)\n",
    "                    elif j == 0:\n",
    "                        tmp.append(DP[i - 1][0])\n",
    "                    else:\n",
    "                        tmp.append(DP[i - 1][j] + tmp[-1])\n",
    "            DP.append(tmp)\n",
    "        return DP[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m, n, countDict = len(obstacleGrid), len(obstacleGrid[0]), {}\n",
    "\n",
    "        def dp(i, j):\n",
    "            if (i, j) in countDict:\n",
    "                return countDict[i, j]\n",
    "            else:\n",
    "                if i >= m or j >= n or obstacleGrid[i][j]:\n",
    "                    return 0\n",
    "                elif i == m-1 and j == n-1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    countDict[i, j] = dp(i, j+1) + dp(i+1, j)\n",
    "                    return countDict[i, j]\n",
    "        return dp(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not obstacleGrid:\n",
    "            return 0\n",
    "        row, col = len(obstacleGrid)-1, len(obstacleGrid[0])-1\n",
    "        self.res = [[-1 for _ in range(col+1)] for _ in range(row+1)]\n",
    "        return self.recur(row, col, obstacleGrid)\n",
    "\n",
    "    def recur(self, row, col, o):\n",
    "        if row == 0 and col == 0:\n",
    "            return 1 if o[0][0] == 0 else 0\n",
    "        elif row < 0 or col < 0:\n",
    "            return 0\n",
    "        elif self.res[row][col] != -1:\n",
    "            return self.res[row][col]\n",
    "        elif o[row][col] == 1:\n",
    "            self.res[row][col] = 0\n",
    "            return 0\n",
    "        else:\n",
    "            left = self.recur(row, col-1, o)\n",
    "            top = self.recur(row-1, col, o)\n",
    "            self.res[row][col] = left+top\n",
    "        return self.res[row][col]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        ob = obstacleGrid\n",
    "        dp = [[0 for i in range(n)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if ob[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                elif i==0 and j==0:\n",
    "                    dp[i][j] = 1\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "#         n = len(obstacleGrid[0])\n",
    "#         print(n)\n",
    "#         m = len(obstacleGrid)\n",
    "#         print(m)\n",
    "#         if (m==1 or n==1) and obstacleGrid[0][0]==1:\n",
    "#             return 0\n",
    "#         dp = [[1] * n for i in range(m)]\n",
    "#         print(dp)\n",
    "#         for i in range(0,m):\n",
    "#             for j in range(0,n):\n",
    "#                 if obstacleGrid[i][j] == 1 and i==0:\n",
    "#                     for k in range(j, n):\n",
    "#                         dp[i][k] = 0\n",
    "#                 if obstacleGrid[i][j] == 1 and j==0:\n",
    "#                     for k in range(i, m):\n",
    "#                         dp[k][j] = 0\n",
    "               \n",
    "#         print(dp)\n",
    "#         for i in range(1,m):\n",
    "#             for j in range(1,n):\n",
    "#                     if obstacleGrid[i][j] == 1:\n",
    "#                                     dp[i][j] = 0\n",
    "#                     else:\n",
    "#                         dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\n",
    "#                     print( dp[i][j])\n",
    "#         return (dp[-1][-1])\n",
    "\n",
    "\n",
    "        n = len(obstacleGrid[0])\n",
    "        m = len(obstacleGrid)       \n",
    "        if (m==1 or n==1) and obstacleGrid[0][0]==1:\n",
    "            return 0\n",
    "        dp = [[1] * n for i in range(m)]      \n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                if obstacleGrid[i][j] == 1 and i==0:\n",
    "                    for k in range(j, n):\n",
    "                        dp[i][k] = 0\n",
    "                if obstacleGrid[i][j] == 1 and j==0:\n",
    "                    for k in range(i, m):\n",
    "                        dp[k][j] = 0                     \n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                    if obstacleGrid[i][j] == 1:\n",
    "                                    dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\n",
    "                    print( dp[i][j])\n",
    "        return (dp[-1][-1])\n",
    "        \n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        cost = [[0 for i in range(len(obstacleGrid[0]))] for i in range(len(obstacleGrid))]\n",
    "\n",
    "        for i in range(len(obstacleGrid)):\n",
    "            for j in range(len(obstacleGrid[0])):\n",
    "                print(i, j)\n",
    "                if obstacleGrid[i][j] == 1:\n",
    "                    cost[i][j] = 0\n",
    "                    continue\n",
    "\n",
    "                if i==0 or j==0:\n",
    "                    if not i == 0:\n",
    "                        cost[i][j] = 1 if cost[i-1][j] == 1 else 0\n",
    "                    elif not j == 0:\n",
    "                        cost[i][j] = 1 if cost[i][j-1] == 1 else 0\n",
    "                    else:\n",
    "                        cost[i][j] = 1\n",
    "                        \n",
    "                else:\n",
    "                    cost[i][j] = cost[i-1][j] + cost[i][j-1]\n",
    "\n",
    "        return cost[len(obstacleGrid)-1][len(obstacleGrid[0])-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid:List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        grid = [[0 for x in range(n)] for y in range(m)]\n",
    "        has_obstacle = False\n",
    "        for col in range(0, n):\n",
    "            if not has_obstacle:\n",
    "                has_obstacle = obstacleGrid[0][col]\n",
    "            if has_obstacle:\n",
    "                grid[0][col] = 0\n",
    "            else:\n",
    "                grid[0][col] = 1\n",
    "\n",
    "        has_obstacle = False\n",
    "        for row in range(0, m):\n",
    "            if not has_obstacle:\n",
    "                has_obstacle = obstacleGrid[row][0]\n",
    "            if has_obstacle:\n",
    "                grid[row][0] = 0\n",
    "            else:\n",
    "                grid[row][0] = 1\n",
    "\n",
    "        for row in range(1,m):\n",
    "            for col in range(1, n):\n",
    "                if obstacleGrid[row][col] == 1:\n",
    "                    grid[row][col] = 0\n",
    "                else:\n",
    "                    grid[row][col] = grid[row-1][col] + grid[row][col-1]\n",
    "\n",
    "        return grid[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        # print (dp)\n",
    "        m = len(obstacleGrid)#[n][m]\n",
    "        n = len(obstacleGrid[0])\n",
    "        print(n,m)\n",
    "        # if m==1 or n==1:\n",
    "        #     print(\"Yes!\")\n",
    "        #     if 1 in obstacleGrid:\n",
    "        #         print(obstacleGrid)\n",
    "        #         return 0\n",
    "        #     else:\n",
    "        #         return 1\n",
    "            \n",
    "        dp = [[0 for i in range(n)] for j in range(m)]\n",
    "        print(dp)\n",
    "        print(obstacleGrid)\n",
    "        for i in range(0,m):\n",
    "            if obstacleGrid[i][0] != 1:\n",
    "                dp[i][0] = 1\n",
    "            else:\n",
    "                if n==0:\n",
    "                    return 0\n",
    "                break\n",
    "        for j in range(0,n):\n",
    "            if obstacleGrid[0][j] != 1:\n",
    "                dp[0][j] = 1\n",
    "            else:\n",
    "                if m==0:\n",
    "                    return 0\n",
    "                break\n",
    "        print(dp)\n",
    "        for j in range(1,m):\n",
    "            for i in range(1, n):\n",
    "                print(i,\" \",j)\n",
    "                if obstacleGrid[j][i]!=1:\n",
    "                    dp[j][i] = dp[j-1][i]+dp[j][i-1]\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recursion(self, d, grid, i, j, m, n):\n",
    "        d[i][j] = d[i-1][j] + d[i][j-1] if not grid[i][j] else 0\n",
    "        if i == m-1 and j == n-1:\n",
    "            return None\n",
    "        elif i == m-1:\n",
    "            self.recursion(d, grid, 1, j+1, m, n)\n",
    "        else:\n",
    "            self.recursion(d, grid, i+1, j, m, n)\n",
    "        return None\n",
    "\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid):\n",
    "        \"\"\"\n",
    "        :type obstacleGrid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        d = [[0 for i in range(n)] for i in range(m)]\n",
    "        d[0][0] = 1 ^ obstacleGrid[0][0];\n",
    "        for i in range(1, m):\n",
    "            d[i][0] = 0 if (obstacleGrid[i][0] or d[i-1][0] == 0) else 1\n",
    "        for i in range(1, n):\n",
    "            d[0][i] = 0 if (obstacleGrid[0][i] or d[0][i-1] == 0) else 1\n",
    "        if m == 1 or n == 1:\n",
    "            return d[m-1][n-1]\n",
    "        self.recursion(d, obstacleGrid, 1, 1, m, n)\n",
    "        return d[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, dp: 'List[List[int]]') -> 'int':\n",
    "        if not dp or not dp[0] or dp[0][0]==1 or dp[len(dp)-1][len(dp[0])-1] ==1 :\n",
    "            return 0\n",
    "        dp[0][0] =1\n",
    "        \n",
    "        \n",
    "        for i in range(len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                if dp[i][j] == 1 and (i!=0 or j!=0):\n",
    "\t\t\t\t\t#Change any obstacles denoted by 1 to -1\n",
    "                    dp[i][j] = -1\n",
    "                    continue\n",
    "                    \n",
    "                if j>0 and dp[i][j-1] != -1:\n",
    "                    dp[i][j] += dp[i][j-1]\n",
    "                \n",
    "                if i>0 and dp[i-1][j] != -1:\n",
    "                    dp[i][j] += dp[i-1][j]\n",
    "                    \n",
    "        return dp[len(dp)-1][len(dp[0])-1]\n",
    "                \n",
    "        \n",
    "#         #Covers all the edge cases\n",
    "#         if not dp or not dp[0] or dp[0][0] == 1 or dp[len(dp)-1][len(dp[0])-1] == 1:\n",
    "#             return 0\n",
    "        \n",
    "        \n",
    "#         #Update the starting position to store 1 as that's the minimum number of ways to reach the end in all cases\n",
    "#         dp[0][0] = 1\n",
    "        \n",
    "#         for i in range(len(dp)):\n",
    "#             for j in range(len(dp[0])):\n",
    "                \n",
    "#                 if dp[i][j] == 1 and (i!=0 or j!=0):\n",
    "# \t\t\t\t\t#Change any obstacles denoted by 1 to -1\n",
    "#                     dp[i][j] = -1\n",
    "#                     continue\n",
    "                \n",
    "#                 if j>0 and dp[i][j-1] != -1:\n",
    "#                     dp[i][j] += dp[i][j-1]\n",
    "                \n",
    "#                 if i>0 and dp[i-1][j] != -1:\n",
    "#                     dp[i][j] += dp[i-1][j]\n",
    "        \n",
    "#         return dp[len(dp)-1][len(dp[0])-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        if(obstacleGrid[0][0]==1 or obstacleGrid[-1][-1]==1):\n",
    "            return 0\n",
    "\n",
    "        n = len(obstacleGrid)\n",
    "        m = len(obstacleGrid[0])\n",
    "        tmp=[0]*m\n",
    "        result=[]\n",
    "        for i in range(n):\n",
    "\n",
    "            result.append(tmp.copy())\n",
    "\n",
    "        result[0][0]=1\n",
    "        print(result)\n",
    "        for i in range(1,n):\n",
    "            result[i][0] = int(obstacleGrid[i][0] == 0 and result[i-1][0] == 1)\n",
    "\n",
    "        # Filling the values for the first row        \n",
    "        for j in range(1, m):\n",
    "            result[0][j] = int(obstacleGrid[0][j] == 0 and result[0][j-1] == 1)\n",
    "        print(result)\n",
    "\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for k in range(1,m):\n",
    "                if (obstacleGrid[i][k]==1):\n",
    "                    result[i][k]=0\n",
    "                else:\n",
    "                    result[i][k]=result[i-1][k] + result[i][k-1]\n",
    "            print(result)\n",
    "        \n",
    "        return result[-1][-1]\n",
    "        \n",
    " \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        if not m:\n",
    "            return 0\n",
    "        \n",
    "        n = len(obstacleGrid[0])\n",
    "        if not n:\n",
    "            return 0\n",
    "\n",
    "        dp = [[0 for _ in range(n)] for __ in range(m)]\n",
    "        dp[0][0] = 0 if obstacleGrid[0][0] else 1\n",
    "\n",
    "        for j in range(1, n):\n",
    "            if obstacleGrid[0][j] == 1:\n",
    "                dp[0][j] = 0\n",
    "            else:\n",
    "                dp[0][j] = dp[0][j - 1]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            if obstacleGrid[i][0] == 1:\n",
    "                dp[i][0] = 0\n",
    "            else:\n",
    "                dp[i][0] = dp[i - 1][0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if obstacleGrid[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\n",
    "\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        if not obstacleGrid[0]:\n",
    "            return 1\n",
    "        n = len(obstacleGrid)\n",
    "        m = len(obstacleGrid[0])\n",
    "        dp = [[0] * m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            if obstacleGrid[0][i] == 1:\n",
    "                break     \n",
    "            dp[0][i] = 1\n",
    "        for j in range(n):\n",
    "            if obstacleGrid[j][0] == 1:\n",
    "                break\n",
    "            dp[j][0] = 1\n",
    "        # dp[j][i] = dp[j-1][i] + dp[j][i-1]\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if obstacleGrid[j][i] != 1:\n",
    "                    dp[j][i] = dp[j-1][i] + dp[j][i-1]\n",
    "        \n",
    "        return dp[-1][-1]\n",
    "\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cache = {}  \n",
    "\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:\n",
    "            return 0\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        self.obstacle = obstacleGrid\n",
    "        return self.uniquePaths(m-1, n-1)\n",
    "\n",
    "    def uniquePaths(self, m: int, n: int) -> int:\n",
    "        if m == 0 and n == 0:\n",
    "            return 1\n",
    "\n",
    "        if m > 0:\n",
    "            if self.obstacle[m-1][n] == 1:\n",
    "                leftResult = 0\n",
    "            else:\n",
    "                if (m-1, n) not in self.cache:\n",
    "                    leftResult = self.uniquePaths(m-1, n)\n",
    "                    self.cache[(m-1, n)] = leftResult\n",
    "                else:\n",
    "                    leftResult = self.cache[(m-1, n)]\n",
    "        else:\n",
    "            leftResult = 0\n",
    "\n",
    "        if n >0 :\n",
    "            if self.obstacle[m][n-1] == 1:\n",
    "                upResult = 0\n",
    "            else:\n",
    "                if (m, n-1) not in self.cache:\n",
    "                    upResult = self.uniquePaths(m, n-1)\n",
    "                    self.cache[(m, n-1)] = upResult\n",
    "                else:\n",
    "                    upResult = self.cache[(m, n-1)]\n",
    "        else:\n",
    "            upResult = 0\n",
    "        return leftResult + upResult"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        if obstacleGrid[0][0]:\n",
    "            return 0\n",
    "        m=len(obstacleGrid)\n",
    "        n=len(obstacleGrid[0])\n",
    "        dp=[[0]*(n+1) for _ in range(m+1)]\n",
    "        dp[1][1]=1\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if i==1 and j==1:\n",
    "                    continue\n",
    "                if obstacleGrid[i-1][j-1]==0:\n",
    "                    dp[i][j]=dp[i-1][j]+dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=0\n",
    "        return dp[-1][-1]\n",
    "                \n",
    "        # if obstacleGrid[0][0]:\n",
    "        #     return 0\n",
    "        \n",
    "        # m = len(obstacleGrid)\n",
    "        # n = len(obstacleGrid[0])\n",
    "        # dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # dp[1][1] = 1\n",
    "\n",
    "        # for  i in range(1,m+1):\n",
    "        #     for j in range(1,n+1):\n",
    "        #         if i==1 and j==1:\n",
    "        #             continue\n",
    "        #         if obstacleGrid[i-1][j-1]==0:\n",
    "        #             dp[i][j]=dp[i-1][j]+dp[i][j-1]\n",
    "        #         else:\n",
    "        #             dp[i][j]=0\n",
    "                    \n",
    "        # return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m, n = len(obstacleGrid[0]), len(obstacleGrid)\n",
    "        dp = [1] + [0] * m \n",
    "        for i in range(0, n):\n",
    "            for j in range(0, m):\n",
    "                dp[j] = 0 if obstacleGrid[i][j] else dp[j] + dp[j-1]\n",
    "        return dp[-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(obstacleGrid[0])\n",
    "        if obstacleGrid[0][0] == obstacleGrid[-1][-1] == 1:\n",
    "            return 0\n",
    "        dp = [1] + [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j] = 0 if obstacleGrid[i][j] else dp[j] + dp[j - 1]\n",
    "        return dp[-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m=len(obstacleGrid)\n",
    "        n=len(obstacleGrid[0])\n",
    "\n",
    "        dp=[[0]*n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            if obstacleGrid[0][j]==1:\n",
    "                break\n",
    "            dp[0][j]=1\n",
    "        for i in range(m):\n",
    "            if obstacleGrid[i][0]==1:\n",
    "                break\n",
    "            dp[i][0]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if obstacleGrid[i][j]!=1:\n",
    "                    dp[i][j]=dp[i-1][j]+dp[i][j-1]\n",
    "        return dp[m-1][n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        dp = [[1 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if obstacleGrid[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i == 0 and j > 0:\n",
    "                        dp[i][j] = min(dp[i][j-1],1)\n",
    "                    elif j == 0 and i > 0:\n",
    "                        dp[i][j] = min(dp[i-1][0],1)\n",
    "                    elif i>0 and j>0:\n",
    "                        dp[i][j] = dp[i-1][j]+ dp[i][j-1]\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        # 典型 dp 问题\n",
    "        rows = len(obstacleGrid)\n",
    "        if rows < 1:return 0\n",
    "\n",
    "        cols = len(obstacleGrid[0])\n",
    "        if cols < 1:return 0\n",
    "\n",
    "        if obstacleGrid[0][0] == 1:return 0\n",
    "        #dp = [[1 for _ in range(cols)] for _ in range(rows)]\n",
    "        dp = [[1]*cols for _ in range(rows)]\n",
    "\n",
    "        #  第一列， 第一行 初始化\n",
    "        for i in range(1, rows): # 必须从1开始\n",
    "            if obstacleGrid[i][0] == 1:\n",
    "                dp[i][0] = 0\n",
    "            else:\n",
    "                if dp[i-1][0] == 0: # 前面有障碍物\n",
    "                    dp[i][0] = 0\n",
    "\n",
    "        for j in range(1, cols): # 必须从1开始\n",
    "            if obstacleGrid[0][j] == 1:\n",
    "                dp[0][j] = 0\n",
    "            else:\n",
    "                if dp[0][j-1] == 0:\n",
    "                    dp[0][j] = 0\n",
    "\n",
    "        # 状态转移 dp[i][j] = dp[i-1][j] + dp[i][j-1] (前一位置转移而来)\n",
    "        for row in range(1, rows):\n",
    "            for col in range(1, cols):\n",
    "                if obstacleGrid[row][col] == 0:\n",
    "                    print(i, j, dp[i-1][j], dp[i][j-1])\n",
    "                    dp[row][col] = dp[row-1][col] + dp[row][col-1]\n",
    "                else:\n",
    "                    dp[row][col] = 0\n",
    "\n",
    "        return dp[rows-1][cols-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        memo = {}\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        def dp(i,j):\n",
    "            if i==0 and j==0:\n",
    "                memo[(0,0)] = 1 if obstacleGrid[0][0]==0 else 0\n",
    "            if (i,j) not in memo:\n",
    "                vi = dp(i-1,j) if i>0 else 0\n",
    "                vj = dp(i,j-1) if j>0 else 0\n",
    "                memo[(i,j)] = vi + vj if obstacleGrid[i][j]==0 else 0\n",
    "            return memo[(i,j)]\n",
    "        return dp(m-1,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        if obstacleGrid[0][0] == 1:  # 容易漏掉\n",
    "            return 0\n",
    "        dp = obstacleGrid[:]\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        # base case\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                elif i == 0 and j == 0:\n",
    "                    dp[i][j] = 1\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "\n",
    "        row = len(obstacleGrid)\n",
    "        column = len(obstacleGrid[0])\n",
    "        dp = [0] * column\n",
    "        dp[0] = 1 if obstacleGrid[0][0] == 0 else 0\n",
    "        for i in range(row):\n",
    "            for j in range(column):\n",
    "                if obstacleGrid[i][j] == 1:\n",
    "                    dp[j] = 0\n",
    "                    continue\n",
    "                #因为取了前一列的值，  j从1开始，需要判断j-1是不是可达，来确定是上一个值还是0\n",
    "                if j > 0 and obstacleGrid[i][j] == 0:\n",
    "                    dp[j] += dp[j - 1]\n",
    "        return dp[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        dp = [[0] * n for i in range(m)]\n",
    "\n",
    "        # 初始化 注意当第0行或第0列出现障碍时，障碍后的所有位置的dp值应初始化为0\n",
    "        for i in range(m):\n",
    "            if obstacleGrid[i][0] == 1:\n",
    "                break\n",
    "            dp[i][0] = 1\n",
    "\n",
    "        for j in range(n):\n",
    "            if obstacleGrid[0][j] == 1:\n",
    "                break\n",
    "            dp[0][j] = 1\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if obstacleGrid[i][j] == 1:\n",
    "                    dp[i][j] = 0\n",
    "                    continue\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
    "        \n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        # 空间复杂度O(n)+代码极简（效率不一定比展开高）        \n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        dp = [1-obstacleGrid[0][0]] + [0]*(n-1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if obstacleGrid[i][j]:\n",
    "                    dp[j] = 0\n",
    "                elif j > 0:\n",
    "                    dp[j] += dp[j-1]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        # 空间复杂度O(n)\n",
    "        if obstacleGrid[0][0]:\n",
    "            return 0\n",
    "        \n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        dp = [1] + [0]*(n-1)\n",
    "        for j in range(1, n):\n",
    "            if obstacleGrid[0][j]:\n",
    "                break\n",
    "            else:\n",
    "                dp[j] = 1\n",
    "        \n",
    "        for i in range(1, m):\n",
    "            if dp[0] and obstacleGrid[i][0]:\n",
    "                dp[0] = 0\n",
    "            for j in range(1, n):\n",
    "                if obstacleGrid[i][j]:\n",
    "                    dp[j] = 0\n",
    "                else:\n",
    "                    dp[j] += dp[j-1]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        dp = [[0]*n for i in range(m)]\n",
    "        for x in range(n):\n",
    "            if obstacleGrid[0][x] != 1:\n",
    "                dp[0][x] = 1\n",
    "            else:\n",
    "                break \n",
    "        for y in range(m):\n",
    "            if obstacleGrid[y][0] != 1:\n",
    "                dp[y][0] = 1\n",
    "            else:\n",
    "                break\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                print(i,j)\n",
    "                if obstacleGrid[i][j] != 1:\n",
    "                    dp[i][j] = dp[i][j-1] + dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "        # print(dp)\n",
    "        return dp[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return 0\n",
    "\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "\n",
    "        dp = obstacleGrid\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                if dp[i][j] == 1:\n",
    "                    dp[i][j] = -1\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for i in range(1, m):\n",
    "            if dp[i][0] == 0:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "            else:\n",
    "                break\n",
    "\n",
    "\n",
    "        for j in range(1, n):\n",
    "            if dp[0][j] == 0:\n",
    "                dp[0][j] = dp[0][j-1]\n",
    "            else:\n",
    "                break\n",
    "\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if dp[i][j] >= 0:\n",
    "                    dp[i][j] = max(dp[i-1][j],0) + max(dp[i][j-1],0)\n",
    "        return max(dp[-1][-1],0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if obstacleGrid[i][j]:\n",
    "                    dp[j] = 0\n",
    "                else:\n",
    "                    dp[j] += dp[j-1]\n",
    "        return dp[-2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        m, n = len(obstacleGrid), len(obstacleGrid[0])\n",
    "        f = [0] * n\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 障碍物的位置方案为0不需要处理\n",
    "                if obstacleGrid[i][j] == 0:\n",
    "                    # 左上角:\n",
    "                    if i == 0 and j == 0:\n",
    "                        f[j] = 1\n",
    "                    else:\n",
    "                        #if i > 0:\n",
    "                            #f[i][j] = f[i - 1][j]\n",
    "                        if j > 0:\n",
    "                            f[j] += f[j - 1]\n",
    "                # 如果为障碍物时重新初始化，否则会沿用上一层的f[j]\n",
    "                else:\n",
    "                    f[j] = 0\n",
    "        return f[n - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:\n",
    "        if obstacleGrid[0][0] == 1:\n",
    "            return 0\n",
    "        m = len(obstacleGrid)\n",
    "        n = len(obstacleGrid[0])\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        check = False\n",
    "        for i in range(n):\n",
    "            if obstacleGrid[0][i] == 1:\n",
    "                check = True\n",
    "            dp[0][i] = 0 if check else 1\n",
    "        check = False\n",
    "        for j in range(m):\n",
    "            if obstacleGrid[j][0] == 1:\n",
    "                check = True\n",
    "            dp[j][0] = 0 if check else 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                dp[i][j] = dp[i-1][j] + dp[i][j-1] if obstacleGrid[i][j] == 0 else 0\n",
    "        return dp[m-1][n-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
